The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Packet forwarding decisions and other packet operations are demanding parts of switch and router design. For example, IP forwarding requires a longest prefix match. In order to support large number of layer 3 prefixes (e.g., IP, IPX), four to eight ternary content-addressable memory (TCAM) chips are often used due to the number of addresses that need to be supported. A longest prefix match is determined by performing a lookup operation on each of the TCAM chips. However, CAMs and TCAMs are expensive in terms of power consumption and heat dissipation, and thus desired are new methods and apparatus for performing lookup operations.